package cn.edu.jxau.test;

import java.util.NoSuchElementException;

/**
 * 基于有序数组的优先队列(priority queue)
 * insert:O(n)
 * delMax:O(1)
 * delMin:O(n)
 * 
 * @author 付大石
 */
public class SortedArrayPQ {

    public static void main(String[] args) {

        SortedArrayPQ pq = new SortedArrayPQ(new int[] { 1, 2, 3, 4, 5 });
        pq.insert(6);
        pq.insert(5);
        pq.insert(2);
        pq.insert(3);
        pq.insert(4);
        pq.insert(2);
        System.out.println(pq.delMax());
        System.out.println(pq.delMax());
        System.out.println(pq.delMin());
    }

    /**
     * 优先队列，升序
     */
    private int[] pq;

    /**
     * 优先队列初始容量
     */
    private static final int INIT_CAPACITY = 10;

    /**
     * 元素个数
     */
    private int size;

    public SortedArrayPQ() {
        pq = new int[INIT_CAPACITY];
    }

    public SortedArrayPQ(int[] elementArr) {

        pq = new int[INIT_CAPACITY];
        for (int element : elementArr) {
            insert(element);
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void insert(int element) {

        if (size == pq.length) {
            resize(pq.length * 2);
        }
        int i = 0;
        for (; i < size; i++) {
            if (element < pq[i]) {
                break;
            }
        }
        if (i == size) { // 无需移动pq
            pq[size] = element;
        } else {
            System.arraycopy(pq, i, pq, i + 1, size - i);
            pq[i] = element;
        }
        size++;
    }

    private void resize(int newCapacity) {

        if (newCapacity < INIT_CAPACITY) {
            return;
        }
        System.out.println("resize to:" + newCapacity);
        int[] temp = new int[newCapacity];
        System.arraycopy(pq, 0, temp, 0, size);
        pq = temp;
    }

    public int delMax() {

        if (isEmpty()) {
            throw new NoSuchElementException("优先队列为空");
        }
        int element = pq[size - 1];
        size--;
        if (size * 4 < pq.length) {
            resize(pq.length / 2);
        }
        return element;
    }

    public int delMin() {

        if (isEmpty()) {
            throw new NoSuchElementException("优先队列为空");
        }
        int element = pq[0];
        size--;
        System.arraycopy(pq, 1, pq, 0, size);
        if (size * 4 < pq.length) {
            resize(pq.length / 2);
        }
        return element;
    }
}
